En esta página puede obtener un análisis detallado de una palabra o frase, producido utilizando la mejor tecnología de inteligencia artificial hasta la fecha:
XOR-обмен (англ. Xor swap algorithm) — алгоритм, в котором используется побитовая операция XOR (исключающее «или») для обмена значениями между переменными, которые содержат данные одного типа, без использования дополнительной (временной) переменной. Решение задачи обеспечивается за счёт свойства самообратимости XOR:
A XOR A = 0 для всех A
.
Алгоритм в псевдокоде:
Это обычно соответствует трём инструкциям в машинном коде, например, в коде ассемблера IBM System/370:
где R1
и R2
— регистры и операция XOR сохраняет результат в первом аргументе.
Алгоритм особенно часто применяется в практике программирования на ассемблере благодаря его эффективности: прочие алгоритмы обмена требуют либо использования промежуточного регистра (дополнительного ресурса хранения), либо (для числовых типов) дополнительных арифметических операций (использования излишних вычислительных ресурсов), что особенно важно при программировании микроконтроллеров и подобных простых устройств, в которых стоят жёсткие требования к расходу памяти и тактов процессора. Некоторые оптимизирующие компиляторы могут генерировать код, использующий этот алгоритм.
Тем не менее, на современных центральных процессорах общего назначения XOR-техника может оказаться медленнее, чем использование временной переменной для обмена в связи c распараллеливанием выполнения команд: в XOR-технике операнды всех команд зависят от результатов предыдущих команд, поэтому они должны быть выполнены в строго последовательном порядке. Зачастую детали используемого алгоритма скрываются внутри макроса или инлайн-функции, и в зависимости от особенностей платформы выполнения выбирается тот или иной алгоритм обмена.
При реализации такого алгоритма обмена существует ряд ошибок-ловушек, в частности, если функция обмена принимает указатели или ссылки и вызвана с одинаковыми аргументами, то произойдёт не обмен, а обнуление данных.
Ряд архитектур реализуют XOR-обмен на аппаратном уровне, первой эффективной реализацией считается машина Datacraft (1970 год), обеспечивавшая обмен любых регистров за один такт. PDP-6 имела такую возможность ещё в 1964; её инструкция EXCH
могла обменивать содержимое любого регистра с содержимым любого участка памяти или другого регистра. Процессоры x86 также имеют инструкцию XCHG.